package com.ssh;

import java.util.Arrays;

import org.junit.Test;

public class SortColors_75 {
	@Test
	public void test() {
		int[] nums = {0,1,2};
		sortColors(nums);
		System.out.println(Arrays.toString(nums));
	}
	
	public void sortColors(int[] nums) {
		sort(nums, 0, nums.length-1);
    }
	
	private void sort(int[] nums, int lo, int hi) {
		if (lo >= hi) {
			return;
		}
		int v = nums[lo];
		int i = lo+1, lt = lo, gt = hi;
		while (i <= gt) {
			if (nums[i] < v) {
				exch(nums, i++, lt++);
			}else if (nums[i] > v) {
				exch(nums, i, gt--);
			}else {
				i++;
			}
		}
		sort(nums, lo, lt-1);
		sort(nums, gt+1, hi);
	}
	private void exch(int[] nums,int x, int y) {
		int t = nums[x];
		nums[x] = nums[y];
		nums[y] = t;
	}
}
